package 贪心;

import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 删除被覆盖区间.java
 * @Description TODO
 * @createTime 2020年10月23日 14:10:00
 * 给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。
 *
 * 只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。
 *
 * 在完成所有删除操作后，请你返回列表中剩余区间的数目。
 *
 *  
 *
 * 示例：
 *
 * 输入：intervals = [[1,4],[3,6],[2,8]]
 * 输出：2
 * 解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。
 *
 * 思路：先按照数组的第一个数升序排序 数组之间只有三种状态：相交 相离 覆盖
 *      滑动窗口+变量记录
 *      先判断第一个元素是否在这个大区间之中 可以拿后一个数的第一个数和前一个数的后一个数进行比较
 *      然后在更新这个区间 每次维护一个窗口 窗口扩大一次就+1 窗口不能扩大就以当前区间为一个新的窗口 持续下去
 */

public class 删除被覆盖区间 {
    public static void main(String[] args) {
    int[][] intervals={{1,4},{3,6},{2,8}};
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {

                return o1[0] == o2[0] ? o2[1] - o1[1]: o1[0] - o2[0];
            }
        });

        int map=0,count=0;
        for(int i=0;i<intervals.length;i++){

            if(map<intervals[i][1]){
                count++;
                map=intervals[i][1];
            }


        }

    }
}
